#include <iostream>
#include <ctime>
#include <vector>
#include <queue>
#include <string>
#include <memory>
#include <functional>
#include <algorithm>
#include <thread>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>

#define QUEUE_NUM 5
#define PROCESS_NUM 20

struct PCB {
    std::string pid_name;   // 进程标识
    char state;             // 进程当前状态
    int priority;           // 进程优先级
    int neededTime;         // 进程运行需要的时间
    int arrivalTime;        // 进程到达的时间
    int usedTime;           // 累计运行时间
    int totalWaitTime;      // 进程等待CPU时间的总和

    PCB(const std::string& pname, char pstate, 
        int ppriority, int pneedTime, int parrival, int utime,int ptotaltime = 0)
        : pid_name(pname),
          state(pstate),
          priority(ppriority),
          neededTime(pneedTime),
          arrivalTime(parrival),
          usedTime(utime),
          totalWaitTime(ptotaltime)
    {}
};

struct Rqueue {
    int number;             // 队列的标号
    int priority;           // 队列优先级
    int timeSlice;          // 队列时间片长度
    std::vector<PCB*> list;      // 存放进程的队列

    using ptr = std::shared_ptr<Rqueue>;

    Rqueue(int ptime, int ts, int num)
        : priority(ptime),
          timeSlice(ts),
          number(num)
    {}
};

class MultiLeveledFeedback {
private:
    // 对sem进行P操作，占用一个信号量
    void P_sem(sem_t& sem) {
        sem_wait(&sem);
    }

    // 释放一个信号量，信号量加加
    void V_sem(sem_t& sem) {
        sem_post(&sem);
    }

    void init() {
        // 初始化队列
        for (int i = 0; i < QUEUE_NUM; i++) {
            rqueue.push_back(Rqueue(i + 1, 10 * (1 << i), i + 1));
        }
        // 初始化信号量
        sem_init(&sem_scheduler, 0, 0);
        pthread_mutex_init(&mutex, nullptr);
    }

    void* generator(void* args) {
        for (int i = 0; i < PROCESS_NUM; i++) {
            int sleep_time = rand() % 100 + 1;
            std::this_thread::sleep_for(std::chrono::microseconds(sleep_time * 1000));
            // usleep(sleep_time * 1000);

            pthread_mutex_lock(&mutex);

            int needTime = rand() % 199 + 2;
            PCB* pcb = new PCB("P" + std::to_string(i), 'w', 1, needTime, Time, 0);
            rqueue[0].list.push_back(pcb);
            printf("Generator: Process %s is generated, neededTime = %d, arrivalTime = %d\n",
                pcb->pid_name.c_str(), pcb->neededTime, pcb->arrivalTime);
            printf("Generator: Sleep for %d ms after generatint next new process\n", sleep_time);

            pthread_mutex_unlock(&mutex);    
        
            // 当scheduler执行结束之后，才会运行下去
            V_sem(sem_scheduler);
        }    
        return nullptr;    
    }

    void updateWaitTime(int sleepTime) {
        for (int i = 0; i < QUEUE_NUM; i++) {
            for (auto& it : rqueue[i].list) 
                it->totalWaitTime += sleepTime;
        }
    }

    void executor(int index) {
        pthread_mutex_lock(&mutex);
        // 从队列中拿出任务
        PCB* task = rqueue[index].list.front();
        auto it = rqueue[index].list.begin();
        rqueue[index].list.erase(it);

        int timeSlice = rqueue[index].timeSlice;
        int sleepTime = (timeSlice + task->usedTime > task->neededTime) ? task->neededTime - task->usedTime : timeSlice;

        std::this_thread::sleep_for(std::chrono::microseconds(sleepTime * 1000));
        // usleep(sleepTime * 1000);
        Time += sleepTime;
        updateWaitTime(sleepTime);

        task->usedTime += sleepTime;
        pthread_mutex_unlock(&mutex);

        printf("Executor: Process %s in queue %d consumes %d ms\n",
            task->pid_name.c_str(), index + 1, sleepTime);   
    }

    void showQueue() {
        for (auto& rq : rqueue) {
            std::cout << "Queue " << rq.number << ":";
            for (auto it : rq.list) {
                std::cout << it->pid_name << " ";
            }
            std::cout << std::endl;
        }
    } 

    void scheduler() {
        int processNum = 0;
        
        P_sem(sem_scheduler);

        // processNum++;
        while (true) {

            for (int i = 0; i < QUEUE_NUM; i++) {
                while (!rqueue[i].list.empty()) {
                    if (sem_trywait(&sem_scheduler) == 0) {
                        // 当前信号量被设置，退出循环，从第一个队列重新开始
                        // 信号量被设置，说明新的进程来临
                        // 最后一个进程进来的时候processNum变为19，并且不会在进入，将会形成死循环
                        // 需要在下文中进行特别的判定
                        processNum++;
                        break;
                    }
                    // 取出队列
                    pthread_mutex_lock(&mutex);
                    PCB* task = rqueue[i].list.front();
                    pthread_mutex_unlock(&mutex);

                    // 执行
                    executor(i);

                    pthread_mutex_lock(&mutex);
                    // 判断当前进程如何处理
                    if (task->pid_name == "P19") 
                        processNum++;
                    
                    if (task->usedTime < task->neededTime) {
                        // 当前进程未执行结束
                        if (task->priority < QUEUE_NUM) {
                            task->priority++;
                            rqueue[i+ 1].list.push_back(task);
                            printf("Scheduler: Process %s is moved to queue %d, priority = %d\n",
                                task->pid_name.c_str(), i + 2, task->priority);
                        } else {
                            // 如果队列已经无法下移，为了确保系统正确运行，则直接丢弃/释放进程。
                            printf("Scheduler: Process %s is running overtime, total waiting time = %d, aborted.\n",
                                task->pid_name.c_str(), task->totalWaitTime);
                            totalWaitTime += task->totalWaitTime;
                            delete task;
                        } 
                    } else {
                        // 进程执行完毕，释放进程
                        printf("Scheduler: Process %s finished, total waiting time = %d\n",
                            task->pid_name.c_str(), task->totalWaitTime);    
                        totalWaitTime += task->totalWaitTime;
                        delete task;
                    }
                    showQueue();
                    pthread_mutex_unlock(&mutex);
                }
            }
            
            // 只有当进程都生产完并且当前队列为空时才退出
            if (processNum > PROCESS_NUM && queueIsEmpty())   
                break;
        }
    }

    bool queueIsEmpty() {
        for (auto& rq : rqueue) {
            if (!rq.list.empty())
                return false;
        }
        return true;
    }
public:
    MultiLeveledFeedback(pthread_t pt)
        : generator_t(pt)
    {
        srand(time(nullptr));
        init();
    }

    void start() {
        auto Generator = [](void* arg) -> void* {
            return static_cast<MultiLeveledFeedback*>(arg)->generator(arg);
        };
        pthread_create(&generator_t, nullptr, Generator, nullptr);
        scheduler();
    }

    void join() {
        pthread_join(generator_t, nullptr);
        std::cout << "The average of total wating time is: " << totalWaitTime / PROCESS_NUM << std::endl;
    }

    ~MultiLeveledFeedback() {
        sem_destroy(&sem_scheduler);
        pthread_mutex_destroy(&mutex);
    }

private:
    pthread_t generator_t;
    pthread_mutex_t mutex;
    double totalWaitTime = 0;
    sem_t sem_scheduler;
    std::vector<Rqueue> rqueue;
    int Time = 0; // 全局时间，用于记录进程执行时消耗的时间
};

int main() {
    pthread_t t;
    MultiLeveledFeedback mul(t);
    mul.start();
    mul.join();
    return 0;
}